#define _CRT_SECURE_NO_WARNINGS 1

#include <vector>
#include <cmath>

using namespace std;

//int determinant(vector<vector<int>> matrix) 
//{
//    int n = matrix.size();
//    if (n == 1) return matrix[0][0];
//    if (n == 2) return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0];
//    int det = 0;
//    for (int j = 0; j < n; j++) 
//    {
//        vector<vector<int>> submat;
//        for (int i = 1; i < n; i++) 
//        {
//            vector<int> row;
//            for (int k = 0; k < n; k++) 
//            {
//                if (k != j) row.push_back(matrix[i][k]);
//            }
//            submat.push_back(row);
//        }
//        int sign = (j % 2 == 0) ? 1 : -1;
//        det += sign * matrix[0][j]  * determinant(submat);
//    }
//    return det;
//}

#include <vector>
#include <sstream>
#include <string>
using namespace std;

string solution(string path) 
{
    if (!path.empty() && path[0] == '~') 
    {
        path = "/home/users/demo" + path.substr(1);
    }
    vector<string> strs;
    stringstream ss(path);
    string item;
    while (getline(ss, item, '/')) 
    {
        if (item.empty() || item == ".") 
        {
            continue;
        }
        else if (item == "..") 
        {
            if (!strs.empty()) strs.pop_back();
        }
        else strs.push_back(item);
    }
    if (strs.empty()) return "/";

    string ret;
    for (const string& comp : strs) ret += "/" + comp;

    return ret;
}

class Solution {
public:
    int numSquares(int n)
    {
        const int INF = 0x3f3f3f3f;
        int m = sqrt(n);
        vector<int> dp(n + 1, 0);

        for (int j = 1; j <= n; j++) dp[j] = INF;
        for (int i = 1; i <= m; i++)
        {
            for (int j = i * i; j <= n; j++)
            {
                dp[j] = min(dp[j], dp[j - i * i] + 1);
            }
        }

        return dp[n];
    }
};

class Solution {
public:
    int GetRob(vector<int>& nums, int left, int right)
    {
        if (left > right) return 0;
        int n = nums.size();
        vector<int> f(n), g(n);
        f[left] = nums[left], g[left] = 0;

        for (int i = left + 1; i <= right; i++)
        {
            f[i] = nums[i] + g[i - 1];
            g[i] = max(f[i - 1], g[i - 1]);
        }

        return max(f[right], g[right]);
    }
    int rob(vector<int>& nums)
    {
        int n = nums.size();
        return max(nums[0] + GetRob(nums, 2, n - 2), GetRob(nums, 1, n - 1));
    }
};

class Solution {
public:
    int rob(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> f(n), g(n);
        f[0] = nums[0], g[0] = 0;

        for (int i = 1; i < n; i++)
        {
            f[i] = nums[i] + g[i - 1];
            g[i] = max(f[i - 1], g[i - 1]);
        }

        return max(f[n - 1], g[n - 1]);
    }
};

class Solution {
public:
    vector<vector<int>> generate(int numRows)
    {
        vector<vector<int>> ret;
        for (int i = 1; i <= numRows; i++)
        {
            vector<int> tmp(i, 1);
            ret.push_back(tmp);
        }

        for (int i = 2; i < numRows; i++)
        {
            for (int j = 1; j < i; j++)
            {
                ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
            }
        }

        return ret;
    }
};

class Solution
{
public:
    vector<int> partitionLabels(string s)
    {
        vector<int> ret;
        int hash[26] = { 0 };

        for (int i = 0; i < s.size(); i++) hash[s[i] - 'a'] = i;

        int far = -1;
        int left = 0;
        for (int i = 0; i < s.size(); i++)
        {
            far = max(far, hash[s[i] - 'a']);
            if (i == far)
            {
                ret.push_back(i - left + 1);
                left = i + 1;
            }
        }

        return ret;
    }
};

class Solution {
public:
    int jump(vector<int>& nums)
    {
        int n = nums.size();
        int left = 0, right = 0;
        int nextright = 0;
        int ret = 0;
        while (nextright < n - 1)
        {
            ret++;
            int nextleft = right + 1;
            for (int i = left; i <= right; i++)
            {
                nextright = max(nextright, i + nums[i]);
            }
            left = nextleft;
            right = nextright;
        }
        return ret;
    }
};